// 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。
// 假设每一种面额的硬币有无限个。 

// int change1(int amount, int* coins, int coinsSize){
//     int i, dp[amount+1];
//     for (i = 1; i <= amount; i++) dp[i] = 0;
//     dp[0] = 1;
// 	for (i = 1; i <= amount; i++) {
//    		for (int j = 0; j < coinsSize; j++) {
//             if (i - coins[j] >= 0) {
//                 dp[i] += dp[i - coins[j]];
//             }
//         }
//     }
//     return dp[amount];
// }

// int change2(int amount, int* coins, int coinsSize){
//     int i, dp[amount+1];
//     for (i = 1; i <= amount; i++) dp[i] = 0;
//     dp[0] = 1;
//     for (int j = 0; j < coinsSize; j++) {
//         for (i = 1; i <= amount; i++) {
//             if (i - coins[j] >= 0) {
//                 dp[i] += dp[i - coins[j]];
//             }
//         }
//     }
//     return dp[amount];
// }


// 以上两个有什么区别？哪个是正确的？
// change1是求的是排列数，可以选择amount次，每次都可以选nums[0]~nums[n-1]；
// change2是求的是组合数，后面的硬币无法使用之前选定的硬币

// 正解为change2





